package sort;

import sort.util.RamdomUtil;

public class QStest {

	public static void sort(int []arr) {
		qSort(arr,0,arr.length-1);
	}
    public static void qSort(int []arr,int p,int r)
    {
    	if(p<r)
    	{
    		int q = partition(arr,p,r);
    		qSort(arr,p,q-1);
    		qSort(arr,q+1,r);
    	}
    }
    
    public static int partition(int []arr,int p,int r)
    {
    	int key=arr[p];
//    	int i=p,j=r+1;
        while(p<r){
            while(arr[r]>=key&&r>p){//�Ӻ�벿����ǰɨ��
                r--;
            }
            arr[p]=arr[r];
            while(arr[p]<=key&&r>p){//��ǰ�벿�����ɨ��
                p++;
            }
            arr[r]=arr[p];
        }
        arr[r]=key;
        return r;
    }
	public static void exchange(int[] a,int i,int j){
//        if(i!=j){
		int temp=a[j];
		a[j]=a[i];
		a[i]=temp;
//        }
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		   int[] arr= RamdomUtil.generateRandomArray(5);
//		for(int x:arr){
//			System.out.print(x+ " ");
//		}
//		System.out.println();
	       long start = System.currentTimeMillis();//
	       qSort(arr,0,arr.length-1);
	       long end = System.currentTimeMillis();//
//			for(int x:arr){
//				System.out.print(x+ " ");
//			}
//			System.out.println();
	       System.out.println("runningtime is :"+(end-start)+"ms");
	       //System.out.println(Arrays.toString(arr));
	}

}
